import collections
import math


class Solution:
    def majorityElement1(self, nums) -> int:
        cnt = collections.Counter(nums)
        len1 = math.ceil(len(nums) / 2)
        for e in cnt:
            if cnt[e] >= len1:
                return e
        return -1

    def majorityElement(self, nums) -> int:
        cnt = 0
        candidate = -1
        for n in nums:
            if cnt == 0:
                candidate = n
            if n == candidate:
                cnt += 1
            else:
                cnt -= 1
        cnt_candidate = nums.count(candidate)
        if cnt_candidate > len(nums) // 2:
            return candidate
        return -1
